#include <iostream>

using namespace std;

#define MAX  99999
int matrix[5][5] = {
    0, 2, 3,  MAX, MAX,
    2, 0, 1, 3, 2,
    3, 1, 0, 5, MAX,
    MAX, 3, 5, 0, 4,
    MAX, 2, MAX, 4, 0
};

typedef int Path[5][5];
typedef int ShortPath[5][5];

int ver_nums = 5;

void floyd(ShortPath D, Path P)
{
    int k, v, w;

    //1.初始化D矩阵和P矩阵
    for (v = 0; v < ver_nums; v++)
        for (w = 0; w < ver_nums; w++) {
            D[v][w] = matrix[v][w];
            P[v][w] = w;
        }


    //2.计算借由k顶点
    for(k = 0; k < ver_nums; k++)
        for (v = 0; v < ver_nums; v++)
            for (w = 0; w < ver_nums; w++)
                if (D[v][w] > D[v][k] + D[k][w]) {
                    D[v][w] = D[v][k] + D[k][w];
                    P[v][w] = P[v][k];
                }

}

void get_path(ShortPath D, Path P, int s, int e)
{
    int k;
    printf("v%d-v%d weight: %d\n", s, e, D[s][e]);

    k = P[s][e];
    printf("path: %d", s);
    while (k!= e) {
        printf(" -> %d", k);
        k = P[k][e];
    }
    printf(" -> %d\n", e);
    printf("\n");
}

void get_path(ShortPath D, Path P)
{
    int k, v, w;
    for(v = 0; v < ver_nums; v++)
        for (w = v + 1; w < ver_nums; w++) {
            printf("v%d-v%d weight: %d\n", v, w, D[v][w]);

            k = P[v][w];
            printf("path: %d", v);
            while (k!= w) {
                printf(" -> %d", k);
                k = P[k][w];
            }
            printf(" -> %d\n", w);
        }
    printf("\n");
}

int main(int argc, char *argv[])
{
    int D[5][5] = {0};
    int P[5][5] = {0};

    floyd(D, P);

//    get_path(D, P);
   get_path(D, P, 0, 4);
   get_path(D, P, 1, 2);
    return 0;
}
